package com.practice.zuocy.base.class12;

/**
 * 【题目】：（TODO：从左到右尝试）
 * 找钱方法数
 */
public class Code09_CoinsWay {

    public static int myWays(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        return myProcess(arr, 0, aim);
    }

    // arr：面值数组
    // 来到了i位置做决定
    // 还剩下rest这么多钱要搞定
    public static int myProcess(int[] arr, int i, int rest) {

        if (i == arr.length && rest == 0) {
            return 1;
        }
        if (i == arr.length && rest != 0) {
            return 0;
        }
        if (rest < 0) {
            return 0;
        }
        if (rest == 0) {
            return 1;
        }
        int res = 0;
        // j代表张
        for (int j = 0; j * arr[i] <= rest; j++) {
            res += myProcess(arr, i + 1, (rest - j * arr[i]));
        }
        return res;
    }

    public static int myDpWay(int[] arr, int aim) {
        // 可变参数i的变换范围：0~N-1
        // 可变参数rest的变化范围：0~aim
        // int[][] dp = new int[N][aim+1]
        // 最后求解的位置：dp[0][aim]
        // 从左往右，从下往上计算
        // 填表
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        for (int i = N - 1; i >= 0; i--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ways = 0;
                // zhang代表张
                for (int zhang = 0; zhang * arr[i] <= rest; zhang++) {
                    ways += dp[i + 1][rest - zhang * arr[i]];
                }
                dp[i][rest] = ways;
            }
        }
        return dp[0][aim];
    }

    // dp优化
    public static int myDpOpt(int[] arr, int aim) {
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        for (int i = N - 1; i >= 0; i--) {
            for (int rest = 0; rest <= aim; rest++) {
                dp[i][rest] = dp[i + 1][rest];
                if (rest - arr[i] > 0) {// 可以往左跳跃
                    dp[i][rest] += dp[i][rest - arr[i]];
                }
            }
        }
        return dp[0][aim];
    }









    
    // arr中都是正数且无重复值，返回组成aim的方法数
    public static int ways1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        return process1(arr, 0, aim);
    }

    public static int process1(int[] arr, int index, int rest) {
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        int ways = 0;
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
            ways += process1(arr, index + 1, rest - (zhang * arr[index]));
        }
        return ways;
    }

    public static int ways2(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int[][] dp = new int[arr.length + 1][aim + 1];
        // 一开始所有的过程，都没有计算呢
        // dp[..][..]  = -1
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        return process2(arr, 0, aim, dp);
    }

    // 如果index和rest的参数组合，是没算过的，dp[index][rest] == -1
    // 如果index和rest的参数组合，是算过的，dp[index][rest]  > - 1
    public static int process2(int[] arr, int index, int rest, int[][] dp) {
        if (dp[index][rest] != -1) {
            // 有直接拿
            return dp[index][rest];
        }
        if (index == arr.length) {
            // 先放缓存在返回
            dp[index][rest] = rest == 0 ? 1 : 0;
            return dp[index][rest];
        }
        int ways = 0;
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
            ways += process2(arr, index + 1, rest - (zhang * arr[index]), dp);
        }
        // 先放缓存在返回
        dp[index][rest] = ways;
        return ways;
    }

    // dp
    public static int ways3(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;// dp[N][1...aim] = 0; 倒数第一行只有dp[N][0]为1，其他为0
        for (int index = N - 1; index >= 0; index--) {// 倒数第二层往上
            for (int rest = 0; rest <= aim; rest++) {// 从左到右
                int ways = 0;
                for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
                    ways += dp[index + 1][rest - (zhang * arr[index])];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }

    // dp优化
    public static int ways4(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;// dp[N][1...aim] = 0;
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                dp[index][rest] = dp[index + 1][rest];// 下面的位置
                if (rest - arr[index] >= 0) {
                    // 下面的位置 + 左边的一个位置
                    dp[index][rest] += dp[index][rest - arr[index]];
                }
            }
        }
        return dp[0][aim];
    }


    public static void main(String[] args) {
        int[] arr = {5, 10, 50, 100};
        int sum = 1000;
        System.out.println(ways1(arr, sum));
        System.out.println(ways2(arr, sum));
        System.out.println(ways3(arr, sum));
        System.out.println(ways4(arr, sum));
        System.out.println("====================");
        System.out.println(myWays(arr, sum));
        System.out.println(myDpWay(arr, sum));
        System.out.println(myDpWay(arr, sum));
    }

}
